package com.YOUtils.Base.YMath;

import java.util.Arrays;
import java.util.Comparator;
import java.util.Objects;

/**
 * Created on 2023/6/13
 *
 * @Time 20:53
 * @Program YOUilt
 * @Author YoHaNe/XiaoShuai
 */
public class YMath {

    public static double square(double n){
        return n * n;
    }

    public static double pow(double n,double index){
        for(;index > 0;index --)
            n*=n;
        return n;
    }

    @Deprecated
    public static double log(double base,double antilogarithm){
        return 0.0;
    }

    public static class Sort{

        private final static int QUICKSORT_THRESHOLD = 286;

        private final static int INSERTION_SORT_THRESHOLD = 47;

        /**
         * InsertSort 插入排序
         * time: O(n2)
         * space: O(1)
         * 稳定性 : 稳定
         * @param array arr
         */
        public static void InsertSort(int[] array){
            for(int i = 1;i < array.length;i++){
                int tmp = array[i];
                int j = i;
                while (j > 0 && tmp < array[j-1]){
                    array[j] = array[j - 1];
                    j--;
                }
                if(j != i)
                    array[j] = tmp;
            }
        }

        /**
         * SelectionSort 选择排序
         * time: O(n2)
         * space: O(1)
         * 稳定性 : 不稳定
         * @param array arr
         */
        public static void SelectionSort(int[] array){
            for(int i=0;i < array.length - 1;i++){
                int min = i;
                for(int j = i+1;j < array.length;j++){
                    if(array[j] < array[min])
                        min = j;
                }
                if(i != min)
                    swap(array,i,min);
            }
        }

        /**
         * BubbleSoft 冒泡排序
         * time: O(n2)
         * space: O(1)
         * 稳定性 : 稳定
         * swap来标识这一轮是否有交换值
         * 如这一轮都没有得话证明数组已经有序可以跳出
         * @param array
         */
        public static void BubbleSoft(int[] array){
            boolean swap;
            for(int i=array.length - 1;i>0;i--){
                swap = false;
                for(int j = 0; j < i;j++){
                    if(array[j] > array[j + 1]) {
                        swap(array, j + 1, j);
                        swap = true;
                    }
                }
                if(!swap)
                    break;
            }
        }

        /**
         * QuickSort 快速排序
         * time: O(nlogn)
         * space: O(nlogn)
         * 稳定性 : 不稳定
         * @param array arr
         */
        public static void QuickSort(int[] array){
            QuickSort(array,0,array.length - 1);
        }

        private static void QuickSort(int[] array,int left,int right){
            if(left < right){
                int partitionIndex = partition(array,left,right);
                QuickSort(array,left,partitionIndex - 1);
                QuickSort(array,partitionIndex + 1,right);
            }
        }

        private static int partition(int[] arr,int left,int right){
            int index = left + 1;
            for(int i=index;i <= right;i++){
                if(arr[i] < arr[left]){
                    swap(arr,i,index);
                    index++;
                }
            }
            swap(arr, left,index - 1);
            return index - 1;
        }

        /**
         * MergeSoft 归并排序
         * time: O(nlogn)
         * space: O(n)
         * 稳定性 : 稳定
         * @param array arr
         */
        public static void MergeSoft(int[] array){
            internalMergeSoft(array,new int[array.length],0,array.length - 1);
        }

        private static void internalMergeSoft(int[] arr,int[] temp,int left,int right){
            if(left < right){
                int mid = (left + right) << 1;
                internalMergeSoft(arr,temp,left,mid);//左数组
                internalMergeSoft(arr,temp,mid + 1,right);//右数组
                mergeSortedArray(arr,temp,left,mid,right);
            }
        }

        private static void mergeSortedArray(int[] arr,int[] temp,int left,int mid,int right){
            int i = left,j = mid + 1,k = 0;
            while (i <= mid && j <= right)
                temp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];
            while (i <= mid)
                temp[k++] = arr[i++];
            while (j <= right)
                temp[k++] = arr[j++];
            for(i = 0;i < k;i++)
                arr[left + i] = temp[i];
        }

        /**
         * 希尔排序 by Knuth
         * time: O(n3/2) / O(nlogn)
         * space: O(nlogn)
         * 稳定性 : 不稳定
         * @param array arr
         */
        public static void ShellSort(int[] array){
            int delta = 1;
            while (delta < array.length / 3)
                delta = delta * 3 + 1;
            for(;delta >= 1;delta /= 3){
                for(int i = delta;i < array.length;i++){
                    for(int j=i;j>=delta && array[j]<array[j-delta];j-=delta)
                        swap(array,j,delta);
                }
            }
        }

        /**
         * CountingSort 计数排序
         * time: O(n + k)
         * space: O(n + k)
         * 稳定性 : 稳定
         * @param array arr
         */
        @SuppressWarnings("all")
        public static void CountingSort(int[] array){
            int max = array[0];
            for(int val : array)
                max = max < val ? val : max;
            CountingSort(array,max);
        }

        private static void CountingSort(int[] arr,int max){
            int bucketLen = max + 1;
            int[] bucket = new int[bucketLen];
            for(int val : arr)
                bucket[val]++;
            int sortedIndex = 0;
            for(int j = 0;j < bucketLen;j++){
                while (bucket[j] > 0){
                    arr[sortedIndex++] = j;
                    bucket[j]--;
                }
            }
        }

        public static void DualPivotQuickSort(int[] arrya){

        }

        private static void DualPivotQuickSort(int[] arr,int left,int right){
            //小于286则使用插入排序和快速排序
           if(right - left < QUICKSORT_THRESHOLD){

            }
        }

        /**
         *
         * @param a arr
         * @param left left
         * @param right right
         * @param leftmost 判断范围是否在最左边
         */
        private static void DPQSort(int[] a,int left,int right,boolean leftmost){
            int length = right - left + 1;
            //如果大于则为快排,否则为插排
            if(length < INSERTION_SORT_THRESHOLD){
                //如果是左区间,则使用原始的插排
                if(leftmost){
                    for(int i = left,j = i;i < length;j = ++i){
                        int ai = a[i + 1];
                        while (ai < a[j]){
                            a[j + 1] = a[j];
                            if(j-- == left)
                                break;
                        }
                        a[j + 1] = ai;
                    }
                }else {
                    //跳过开头的升序部分l
                    do{
                        if(left >= right)
                            return;
                    }while (a[++left] >= a[left - 1]);
                }
            }
        }

        private static void swap(int[] arr,int i,int j){
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
}
